[数据结构与算法] 二叉树简介

发表于 | 分类于 ， |

介绍

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有 N 个节点和 N-1 条边的一个有向无环图。

二叉树 是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有 两个子树 的树结构，通常子树被称作 “左子树” 和 “右子树”。

本文主要介绍二叉树的表示方法、二叉树的三种遍历方式以及如何构造一棵二叉树。

二叉树的表示

在C++中，我们使用一个结构体来表示二叉树，包括：当前节点的值（val），左子树指针（TreeNode left），右子树指针（TreeNode right），结构体的构造函数（ TreeNode(int x) ），代码如下：

1
2
3
4
5
6
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

本文的所有代码，默认使用此结构体表示二叉树。

二叉树的遍历

我们经常希望访问树中的每一个结点并且查看它的值。有很多常见的顺序来访问所有的结点，而且每一种都有有用的性质。

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。其中，“前序”、“中序”、“后序”指的是访问根节点的顺序。L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数

  • 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
  • 中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。
  • 后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

在下图这个二叉树中，

  • 前序遍历的结果：M，G，D，B，A，C，F，E，J，H，I，K，L，S，P，O，N，Q，R，W，U，T，V，X，Z，Y
  • 后序遍历的结果：A，C，B，E，F，D，I，H，L，K，J，G，N，O，R，Q，P，T，V，U，Y，Z，X，W，S，M
  • 中序遍历的结果：A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U，V，W，X，Y，Z

下面介绍三种遍历方法的C++实现

二叉树的前序遍历

[LeetCode 144] 二叉树的前序遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
   
    vector<int> result;
    
    if(root != NULL){
        result.push_back(root->val);
        
        vector<int> left = preorderTraversal(root->left);
        result.insert(result.end(), left.begin(), left.end());
        
        vector<int> right = preorderTraversal(root->right);
        result.insert(result.end(), right.begin(), right.end());
        
        }
        
    return result;
    }
};

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == NULL)
        {
            return result;
        }
        std::stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        while(!nodeStack.empty())
        {
            // 先遍历根节点
            TreeNode *node = nodeStack.top();
            result.push_back(node->val);
            nodeStack.pop();
            // 先将当前节点的右子树压入栈中，
            // 然后压入左子树
            // 这样就可以先遍历左子树
            if(node->right)
            {
                nodeStack.push(node->right);
            }
            if(node->left)
            {
                nodeStack.push(node->left);
            }
        }
        return result;
    }
};

二叉树的中序遍历

[LeetCode 94] 二叉树的中序遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root!=NULL){
            vector<int> left = inorderTraversal(root->left);
            result.insert(result.end(), left.begin(), left.end());
        
            result.push_back(root->val);
        
            vector<int> right = inorderTraversal(root->right);
            result.insert(result.end(), right.begin(), right.end());
        }  
    return result;
    }
};

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == NULL)
        {
            return result;
        }
        std::stack<TreeNode*> nodeStack;
        while (!nodeStack.empty() || root != NULL) {
            if (root != NULL) {
                // 将左子树的节点依次入栈
                nodeStack.push(root);
                root = root->left;
            }
            // 访问到叶子节点
            else {
                // 将栈顶节点的数值放入result中
                root = nodeStack.top();
                result.push_back((nodeStack.top())->val);
                nodeStack.pop();
                // 栈顶节点（相当于当前的根节点）已被遍历，然后遍历右子树
                // 如果root->right为null，说明当前节点无右子树，
                // 下一轮循环，栈顶元素弹出，遍历其父节点
                root = root->right;
            }
        }
        return result;
    }
};

二叉树的后序遍历

[LeetCode 145] 二叉树的后序遍历

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root!=NULL){
            vector<int> left = postorderTraversal(root->left);
            result.insert(result.end(), left.begin(), left.end());
        
            vector<int> right = postorderTraversal(root->right);
            result.insert(result.end(), right.begin(), right.end());
        
            result.push_back(root->val);   
    }
        return result;
    }
};

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stack;
        vector<int> result;
        if(!root) return result;
        stack.push(root);
        while(!stack.empty()) {
            TreeNode *node = stack.top();
            if(!node->left&&!node->right) {
                result.push_back(node->val);
                stack.pop();
            }
            if(node->right) {
                stack.push(node->right);
                node->right = NULL;
            }
            if(node->left) {
                stack.push(node->left);
                node->left = NULL;
            }
        }
        return result;
    }     
};

二叉树的构造

二叉树的构造，相当于二叉树遍历的逆过程：给出一棵二叉树的遍历序列，还原此二叉树。
注意：只有同时给出中序遍历和后序遍历，或者前序遍历和中序遍历才能确定一棵二叉树。

根据一棵树的前序遍历与中序遍历构造二叉树

[LeetCode 105] 从前序与中序遍历序列构造二叉树
例如：给出前序遍历 preorder = [3,9,20,15,7] 和中序遍历 inorder = [9,3,15,20,7]，返回二叉树。

分析一下：
首先根据前序遍历，可以知道根节点为3，然后在中序遍历中找到3，很显然3将中序遍历一分为二：3左边的为根节点的左子树部分，3右边的为根节点的右子树部分。同样，左子树和右子树的根节点也用类似的方法找到。这其实是一个递归的问题。
那么我们可以首先创建root，然后root->left与root->right可以递归地创建，多说无益看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return TreeConstruct(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
}
    TreeNode* TreeConstruct(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir){
        if(pl>pr || il>ir){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[pl]);
        for(int k = il; k <= ir; k++){
            if(preorder[pl] == inorder[k]){
                root->left = TreeConstruct(preorder, pl+1, pl+k-il, inorder, il, k-1);
                root->right = TreeConstruct(preorder, pl+k-il+1, pr, inorder, k+1, ir);
            }
        }
        return root;
    }
};

根据一棵树的中序遍历与后序遍历构造二叉树

[LeetCode 106] 从中序与后序遍历序列构造二叉树
分析过程与之前类似，也是通过后序遍历找到根节点，然后将中序遍历一分为二，递归创建root->left与root->right。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return ConstrucTree(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
    }
    TreeNode* ConstrucTree(vector<int>& inorder, int il, int ir,vector<int>& postorder,int pl, int pr){
        if(il>ir || pl>pr)
            return NULL;
        TreeNode* root = new TreeNode(postorder[pr]);
        for(int k=il; k<=ir; k++){
            if(inorder[k] == postorder[pr]){
                root->left = ConstrucTree(inorder, il, k-1, postorder, pl, pl+k-il-1);
                root->right = ConstrucTree(inorder, k+1, ir, postorder, pl+k-il, pr-1);
            }
        }
        return root;
    }
};